{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最大矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #dynamic-programming #matrix #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #动态规划 #矩阵 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximalRectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由&nbsp;<code>0</code> 和 <code>1</code>&nbsp;组成的矩阵 <code>matrix</code>&nbsp;，找出只包含 <code>1</code> 的最大矩形，并返回其面积。</p>\n",
    "\n",
    "<p><strong>注意：</strong>此题 <code>matrix</code>&nbsp;输入格式为一维 <code>01</code> 字符串数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg\" style=\"width: 402px; height: 322px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [&quot;10100&quot;,&quot;10111&quot;,&quot;11111&quot;,&quot;10010&quot;]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>最大矩形如上图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = []\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [&quot;0&quot;]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [&quot;1&quot;]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [&quot;00&quot;]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rows == matrix.length</code></li>\n",
    "\t<li><code>cols == matrix[0].length</code></li>\n",
    "\t<li><code>0 &lt;= row, cols &lt;= 200</code></li>\n",
    "\t<li><code>matrix[i][j]</code> 为 <code>&#39;0&#39;</code> 或 <code>&#39;1&#39;</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 85 题相同（输入参数格式不同）：&nbsp;<a href=\"https://leetcode-cn.com/problems/daily-temperatures/\">https://leetcode-cn.com/problems/maximal-rectangle/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [PLYXKQ](https://leetcode.cn/problems/PLYXKQ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [PLYXKQ](https://leetcode.cn/problems/PLYXKQ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"10100\",\"10111\",\"11111\",\"10010\"]', '[]', '[\"0\"]', '[\"1\"]', '[\"00\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "\n",
    "        def max_rectangle(heights):\n",
    "            stack = []\n",
    "            i = 0\n",
    "            res = 0\n",
    "            n = len(heights)\n",
    "            while i<n:\n",
    "                if not stack or heights[stack[-1]]<=heights[i]:\n",
    "                    stack.append(i)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    poped = stack.pop()\n",
    "                    width = i if not stack else i-stack[-1]-1\n",
    "                    res = max(res,width*heights[poped])\n",
    "            while stack:\n",
    "                poped = stack.pop()\n",
    "                width = i if not stack else i-stack[-1]-1\n",
    "                res = max(res,width*heights[poped])\n",
    "            return res\n",
    "        \n",
    "        M = matrix\n",
    "        if not M:\n",
    "            return 0\n",
    "        m = len(M)\n",
    "        n = len(M[0])\n",
    "        dp = [0]*n\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = 0 if M[i][j]=='0' else dp[j]+1\n",
    "            max_current = max_rectangle(dp)\n",
    "            ans = max(ans,max_current)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        height = [0] * n\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    height[j] += 1\n",
    "                else:\n",
    "                    height[j] = 0\n",
    "            \n",
    "            stack = [(-1, 0)]\n",
    "            for j in range(n):\n",
    "                while stack and stack[-1][1] >= height[j]:\n",
    "                    stack.pop()\n",
    "                curr = last = height[j]\n",
    "                for (k, h) in stack[::-1]:\n",
    "                    curr = max(curr, (j - k) * last)\n",
    "                    last = h\n",
    "                \n",
    "                stack.append((j, height[j]))\n",
    "                ret = max(ret, curr)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        # import sys\n",
    "        # if not matrix:\n",
    "        #     return 0\n",
    "        # M = len(matrix)\n",
    "        # N = len(matrix[0])\n",
    "\n",
    "        # def ContinuousOne(row):\n",
    "        #     res = [0] * (N + 1)\n",
    "        #     for i in range(N):\n",
    "        #         if row[i] == \"1\":\n",
    "        #             res[i + 1] = res[i] + 1\n",
    "        #     return res[1:]\n",
    "        # ContinuousMatrix = []\n",
    "        # for row in matrix:\n",
    "        #     ContinuousMatrix.append(ContinuousOne(row))\n",
    "        # res = 0\n",
    "        # for i in range(M):\n",
    "        #     for j in range(N):\n",
    "        #         # check every point\n",
    "        #         minContinuousOne = sys.maxsize\n",
    "        #         for p in range(i, -1, -1):\n",
    "        #             minContinuousOne = min(\n",
    "        #                 minContinuousOne, ContinuousMatrix[p][j])\n",
    "        #             tmp = minContinuousOne * (i - p + 1)\n",
    "        #             res = max(res, tmp)\n",
    "        # return res\n",
    "\n",
    "        def largestRectangleArea(heights):\n",
    "            heights = [0] + heights + [0]\n",
    "            n = len(heights)\n",
    "            stack = []\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur_h = heights[stack.pop()]\n",
    "                    cur_s = cur_h * (i - stack[-1] - 1)\n",
    "                    res = max(res, cur_s)\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        res = 0\n",
    "        M = len(matrix)\n",
    "        N = len(matrix[0])\n",
    "        heights = [0] * N\n",
    "        for j in range(N):\n",
    "            if matrix[0][j] == \"1\":\n",
    "                heights[j] = 1\n",
    "        res = max(res, largestRectangleArea(heights))\n",
    "        for i in range(1, M):\n",
    "            for j in range(N):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    heights[j] += 1\n",
    "                else:\n",
    "                    heights[j] = 0\n",
    "            res = max(res, largestRectangleArea(heights))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        h = [0]*(n+1)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            st = [-1]\n",
    "            for j in range(n):\n",
    "                h[j] = h[j]+1 if matrix[i][j]=='1' else 0\n",
    "                while h[st[-1]]>h[j]:\n",
    "                    idx = st.pop()\n",
    "                    ans = max(ans,h[idx]*(j-1-st[-1]))\n",
    "                st.append(j)\n",
    "            while h[st[-1]]>0:\n",
    "                idx = st.pop()\n",
    "                ans = max(ans,h[idx]*(j-st[-1]))            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        result = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '0':\n",
    "                    dp[j] = 0\n",
    "                else:\n",
    "                    dp[j] += 1\n",
    "            result = max(result, self.maxArea(dp))\n",
    "        return result\n",
    "\n",
    "    def maxArea(self, heights):\n",
    "        heights = [0] + heights + [0]\n",
    "        n = len(heights)\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            while heights[i] < heights[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                hight = heights[top]\n",
    "                width = i - stack[-1] - 1\n",
    "                res = max(res, hight * width)\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix) -> int:\n",
    "        if len(matrix)==0:\n",
    "            return 0\n",
    "        maxnum=0\n",
    "        list=[0 for i in range(len(matrix[0]))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                list[j]=int(matrix[i][j]) *(list[j]+1)\n",
    "            maxnum=max(maxnum,self.largestRectangleArea(list))\n",
    "\n",
    "\n",
    "        return maxnum\n",
    "\n",
    "\n",
    "    def largestRectangleArea(self, heights) -> int:\n",
    "        list=[-1]\n",
    "        max=0\n",
    "        for i in range(len(heights)):\n",
    "            if len(list)==1 or heights[i]>heights[list[-1]]:\n",
    "                list.append(i)\n",
    "            else:\n",
    "                while len(list)>1 and heights[i]<=heights[list[-1]]:\n",
    "                    k=list.pop()\n",
    "                    now=heights[k]*(i-1-list[-1])\n",
    "                    if now>max:\n",
    "                        max=now\n",
    "                list.append(i)\n",
    "        while len(list)>1:\n",
    "            k=list.pop()\n",
    "            now=heights[k]*(len(heights)-1-list[-1])\n",
    "            if now > max:\n",
    "                max = now\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        def mat(i,j):\n",
    "            for q in range(j,n):\n",
    "                if matrix[i][q] == '0':\n",
    "                    break\n",
    "            else:\n",
    "                q += 1\n",
    "            res = q-j\n",
    "\n",
    "            for p in range(i+1,m):\n",
    "                for t in range(j,q):\n",
    "                    if matrix[p][t] =='0':\n",
    "                        res= max(res,(p-i+1)*(t-j))\n",
    "                        q = t\n",
    "                        break\n",
    "                else:\n",
    "                    res=max(res,(p-i+1)*(q-j))\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    res = max(res,mat(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        def mat(i,j):\n",
    "            for q in range(j,n):\n",
    "                if matrix[i][q] == '0':\n",
    "                    break\n",
    "            else:\n",
    "                q += 1\n",
    "            res = q-j\n",
    "\n",
    "            for p in range(i+1,m):\n",
    "                for t in range(j,q):\n",
    "                    if matrix[p][t] =='0':\n",
    "                        res= max(res,(p-i+1)*(t-j))\n",
    "                        q = t\n",
    "                        break\n",
    "                else:\n",
    "                    res=max(res,(p-i+1)*(q-j))\n",
    "            return res\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    res = max(res,mat(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def largestRectangleArea(heights) -> int:\n",
    "    '''\n",
    "    剑指 Offer II 039. 直方图最大矩形面积\n",
    "    '''\n",
    "    stack=[(-1,-1)]\n",
    "    H=heights+[0]\n",
    "    ans=0\n",
    "    for i,h in enumerate(H):\n",
    "        while stack[-1][1]>h:\n",
    "            _,oh = stack.pop()\n",
    "            s=(i-stack[-1][0]-1)*oh\n",
    "            ans=max(ans,s)\n",
    "        stack.append((i,h))\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        M=matrix\n",
    "        if not M:\n",
    "            return 0\n",
    "        m=len(M)\n",
    "        n=len(M[0])\n",
    "        dp = [0]*n\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = 0 if M[i][j]=='0' else dp[j]+1\n",
    "            ans = max(ans,largestRectangleArea(dp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:return 0\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        pre=[0]*(n+1)\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[j]=pre[j]+1 if matrix[i][j]==\"1\" else 0\n",
    "            stack=[-1]\n",
    "            for k,num in enumerate(pre):\n",
    "                while stack and pre[stack[-1]]>num:\n",
    "                    index=stack.pop()\n",
    "                    res=max(res,pre[index]*(k-stack[-1]-1))\n",
    "                stack.append(k)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or len(matrix) == 0:\n",
    "            return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        tot = [0] * m\n",
    "        for row in matrix:\n",
    "            for j, x in enumerate(row):\n",
    "                if x == '0':\n",
    "                    tot[j] = 0\n",
    "                else:\n",
    "                    tot[j] += 1\n",
    "            left, right = [-1] * m, [m] * m\n",
    "            stk = []\n",
    "            for i, x in enumerate(tot):\n",
    "                while stk and tot[stk[-1]] >= x:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    left[i] = stk[-1]\n",
    "                stk.append(i)\n",
    "            stk = []\n",
    "            for i in range(m-1, -1, -1):\n",
    "                while stk and tot[stk[-1]] > tot[i]:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    right[i] = stk[-1]\n",
    "                stk.append(i)\n",
    "                ans = max(ans, tot[i] * (right[i] - left[i] - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        n = len(matrix)\n",
    "        if n > 0:\n",
    "            m = len(matrix[0])\n",
    "        else:\n",
    "            return 0\n",
    "        height = [0 for _ in range(m+1)]\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for row in matrix:\n",
    "            stack = []\n",
    "            for i in range(m+1):\n",
    "                if i < m :\n",
    "                    if row[i] == '1':\n",
    "                        height[i] += 1\n",
    "                    else:\n",
    "                        height[i] = 0\n",
    "                while len(stack) and height[stack[-1]]>=height[i]:\n",
    "                    cur_idx = stack[-1]\n",
    "                    r_idx = i\n",
    "                    stack.pop()\n",
    "                    \n",
    "                    l_idx = stack[-1] if len(stack) else -1\n",
    "                    # print(l_idx, r_idx, cur_idx, height)\n",
    "                    res = max(res, (r_idx-l_idx-1)*height[cur_idx])\n",
    "                stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [0] * (n + 1)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[j] = pre[j] + 1 if matrix[i][j] == '1' else 0\n",
    "            stack = [-1]\n",
    "            for k , num in enumerate(pre):\n",
    "                while stack and pre[stack[-1]] > num:\n",
    "                    index = stack.pop()\n",
    "                    res = max(res, pre[index] * (k - stack[-1] - 1))\n",
    "                stack.append(k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        n=len(matrix)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        m=len(matrix[0])\n",
    "        heights=[0]*m\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j]==\"1\":\n",
    "                    heights[j]+=1\n",
    "                else:\n",
    "                    heights[j]=0\n",
    "            res=max(res, self.listmax(heights))\n",
    "        return res\n",
    "    \n",
    "    def listmax(self, heights):\n",
    "        res=0\n",
    "        n=len(heights)\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            while len(stack) and heights[i]<heights[stack[-1]]:\n",
    "                index=stack.pop()\n",
    "                height=heights[index]\n",
    "                if len(stack)>0:\n",
    "                    width=i-stack[-1]-1\n",
    "                else:\n",
    "                    width=i\n",
    "                res=max(res, width*height)\n",
    "            stack.append(i)\n",
    "        while len(stack):\n",
    "            index=stack.pop()\n",
    "            height=heights[index]\n",
    "            if len(stack)>0:\n",
    "                width=n-stack[-1]-1\n",
    "            else:\n",
    "                width=n\n",
    "            res=max(res, width*height)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def largestRectangleArea(heights: List[int]) -> int:\n",
    "            # 建立一个单调递增的栈,\n",
    "            # 遇到新元素比他小的时候，开始求以栈顶数为高的面积，其左边界为栈顶的第二个数，右边界为当前数(左右都不包含)。\n",
    "            stack = [-1]\n",
    "            ans = 0\n",
    "            for i, height in enumerate(heights):\n",
    "\n",
    "                while len(stack) > 1 and heights[stack[-1]] > height:\n",
    "                    ans = max(ans, heights[stack.pop()] * (i - stack[-1] - 1))\n",
    "                stack.append(i)\n",
    "\n",
    "            for i in range(len(stack) -1):\n",
    "                ans = max(ans, heights[stack.pop()] * (len(heights) - stack[-1] - 1))\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        heights = [0] * len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                heights[j] = heights[j] + 1 if matrix[i][j] == \"1\" else 0\n",
    "            res = max(res, largestRectangleArea(heights))\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def maxheight(height: List, res: int):\n",
    "            stack = [-1]   \n",
    "            for i, num in enumerate(height):\n",
    "                while stack[-1] != -1 and height[stack[-1]] > num:\n",
    "                    pre_i = stack.pop()\n",
    "                    res = max(res, (i - stack[-1] - 1) * height[pre_i])\n",
    "                stack.append(i)\n",
    "            while stack[-1] != -1:\n",
    "                pre_i = stack.pop()\n",
    "                res = max(res, (len(height) - stack[-1] - 1) * height[pre_i])\n",
    "            return res\n",
    "        if not matrix: return 0\n",
    "        heights, ans = [0] * len(matrix[0]), 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '0':\n",
    "                    heights[j] = 0\n",
    "                elif i > 0 and matrix[i - 1][j] == '0':\n",
    "                    heights[j] = int(matrix[i][j])\n",
    "                else: heights[j] += 1\n",
    "            ans = maxheight(heights, ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        # import sys\n",
    "        # if not matrix:\n",
    "        #     return 0\n",
    "        # M = len(matrix)\n",
    "        # N = len(matrix[0])\n",
    "\n",
    "        # def ContinuousOne(row):\n",
    "        #     res = [0] * (N + 1)\n",
    "        #     for i in range(N):\n",
    "        #         if row[i] == \"1\":\n",
    "        #             res[i + 1] = res[i] + 1\n",
    "        #     return res[1:]\n",
    "        # ContinuousMatrix = []\n",
    "        # for row in matrix:\n",
    "        #     ContinuousMatrix.append(ContinuousOne(row))\n",
    "        # res = 0\n",
    "        # for i in range(M):\n",
    "        #     for j in range(N):\n",
    "        #         # check every point\n",
    "        #         minContinuousOne = sys.maxsize\n",
    "        #         for p in range(i, -1, -1):\n",
    "        #             minContinuousOne = min(\n",
    "        #                 minContinuousOne, ContinuousMatrix[p][j])\n",
    "        #             tmp = minContinuousOne * (i - p + 1)\n",
    "        #             res = max(res, tmp)\n",
    "        # return res\n",
    "\n",
    "        def largestRectangleArea(heights):\n",
    "            heights = [0] + heights + [0]\n",
    "            n = len(heights)\n",
    "            stack = []\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur_h = heights[stack.pop()]\n",
    "                    cur_s = cur_h * (i - stack[-1] - 1)\n",
    "                    res = max(res, cur_s)\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        res = 0\n",
    "        M = len(matrix)\n",
    "        N = len(matrix[0])\n",
    "        heights = [0] * N\n",
    "\n",
    "        for i in range( M):\n",
    "            for j in range(N):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    heights[j] += 1\n",
    "                else:\n",
    "                    heights[j] = 0\n",
    "            res = max(res, largestRectangleArea(heights))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def maxheight(height: List, res: int):\n",
    "            stack = [-1]   \n",
    "            for i, num in enumerate(height):\n",
    "                while stack[-1] != -1 and height[stack[-1]] > num:\n",
    "                    pre_i = stack.pop()\n",
    "                    res = max(res, (i - stack[-1] - 1) * height[pre_i])\n",
    "                stack.append(i)\n",
    "            while stack[-1] != -1:\n",
    "                pre_i = stack.pop()\n",
    "                res = max(res, (len(height) - stack[-1] - 1) * height[pre_i])\n",
    "            return res\n",
    "        if not matrix: return 0\n",
    "        heights, ans = [0] * len(matrix[0]), 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '0':\n",
    "                    heights[j] = 0\n",
    "                elif i > 0 and matrix[i - 1][j] == '0':\n",
    "                    heights[j] = int(matrix[i][j])\n",
    "                else: heights[j] += 1\n",
    "            ans = maxheight(heights, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        dp = [0 for _ in range(m)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == '0':\n",
    "                    dp[j] = 0\n",
    "                else:\n",
    "                    dp[j] += 1\n",
    "            res = max(res, self.maxArea(dp))\n",
    "        return res\n",
    "    \n",
    "    def maxArea(self, heights):\n",
    "        heights = [0] + heights + [0]\n",
    "        n = len(heights)\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            while heights[i] < heights[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                h = heights[top]\n",
    "                w = i - stack[-1] - 1\n",
    "                res = max(res, h * w)\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        result = 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[j][i] == '0':\n",
    "                    dp[j] = 0\n",
    "                else:\n",
    "                    dp[j] += 1\n",
    "            result = max(result, self.maxArea(dp))\n",
    "        return result\n",
    "\n",
    "    def maxArea(self, heights):\n",
    "        heights = [0] + heights + [0]\n",
    "        n = len(heights)\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            while heights[i] < heights[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                hight = heights[top]\n",
    "                width = i - stack[-1] - 1\n",
    "                res = max(res, hight * width)\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def area(row):\n",
    "            stack = [0]\n",
    "            row = [0]+row+[0]\n",
    "            n = len(row)\n",
    "            ans = 0\n",
    "            for i in range(1,n):\n",
    "\n",
    "                while row[stack[-1]]>row[i]:\n",
    "                    tmp = stack.pop()\n",
    "                    ans = max(ans,row[tmp]*(i-stack[-1]-1))\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        row = [0]*m\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            row = [row[j]+1 if matrix[i][j]=='1' else 0 for j in range(m)]\n",
    "            ans = max(ans,area(row))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "\n",
    "        str_list = [''.join(i) for i in matrix]\n",
    "        nums =[int(i,base = 2) for i in  str_list]\n",
    "\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            new_num = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                new_num = new_num & nums[j]\n",
    "                width =  self.getWidth(new_num)\n",
    "                if (j-i+1) * width > res :\n",
    "                    res = (j-i+1) * width\n",
    "        return res\n",
    "    \n",
    "    def getWidth(self, num):\n",
    "        res = 0\n",
    "        while(num > 0) :\n",
    "            num &= num << 1\n",
    "            res +=1\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        a = matrix\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        row = [0] * n\n",
    "        for i in range(m):\n",
    "            for k in range(n):\n",
    "                if a[i][k] == '1':\n",
    "                    row[k] += 1\n",
    "                else:\n",
    "                    row[k] = 0\n",
    "            # 1,0,1,0,0\n",
    "            # 2,0,2,1,1\n",
    "            # 3,1,3,2,2\n",
    "            l, r = [-1] * n, [n] * n\n",
    "            st = []\n",
    "            tmp = row[:]\n",
    "            for i in range(n):\n",
    "                while st and tmp[st[-1]] > tmp[i]:\n",
    "                    r[st[-1]] = i\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    if tmp[i] > tmp[st[-1]]:\n",
    "                        l[i] = st[-1]\n",
    "                    elif tmp[i] == tmp[st[-1]]:\n",
    "                        l[i] = l[st[-1]]\n",
    "                st.append(i) \n",
    "            for i in range(n):\n",
    "                ans = max(ans, row[i] * (r[i] - l[i] - 1))\n",
    "            # print(f'{row},{l}, {r}, {st}, {ans}')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        height = [0] * n\n",
    "        ret = 0\n",
    "\n",
    "        def func(heights):\n",
    "            n = len(heights)\n",
    "\n",
    "            left = [0] * n\n",
    "            stack = [(-1, 0)]\n",
    "            for i, h in enumerate(heights):\n",
    "                while stack and stack[-1][1] >= h:\n",
    "                    stack.pop()\n",
    "                left[i] = stack[-1][0] + 1 if stack else i\n",
    "                stack.append((i, h))\n",
    "            \n",
    "            right = [0] * n\n",
    "            stack = [(n, 0)]\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                h = heights[i]\n",
    "                while stack and stack[-1][1] >= h:\n",
    "                    stack.pop()\n",
    "                right[i] = stack[-1][0] - 1 if stack else i\n",
    "                stack.append((i, h))\n",
    "            \n",
    "            ret = 0\n",
    "            for i in range(n):\n",
    "                ret = max(ret, (right[i] - left[i] + 1) * heights[i])\n",
    "            return ret\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    height[j] += 1\n",
    "                else:\n",
    "                    height[j] = 0\n",
    "            \n",
    "            ret = max(ret, func(height))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0 \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        preSum = [0] * (n+1)\n",
    "\n",
    "        res = 0 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    preSum[j] += 1\n",
    "                else:\n",
    "                    preSum[j] = 0 \n",
    "        \n",
    "            stack = []\n",
    "            stack.append(-1)\n",
    "            for k, num in enumerate(preSum):\n",
    "                while stack and preSum[stack[-1]] > num:\n",
    "                    idx = stack.pop()\n",
    "                    res = max(res, preSum[idx] * (k-stack[-1]-1))\n",
    "                stack.append(k)\n",
    "            \n",
    "        return res \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def largestRectangleArea(heights)->int:\n",
    "    stack=[(-1,-1)]\n",
    "    H=heights+[0]\n",
    "    ans=0\n",
    "    for i,h in enumerate(H):\n",
    "        while stack and stack[-1][1]>h:\n",
    "            _,oh=stack.pop()\n",
    "            s=(i-stack[-1][0]-1)*oh\n",
    "            ans=max(ans,s)\n",
    "        stack.append((i,h))\n",
    "    return ans \n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        M=matrix\n",
    "        if not M:\n",
    "            return 0\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        dp=[0]*n\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j]=0 if matrix[i][j]=='0' else dp[j]+1\n",
    "            ans=max(ans,largestRectangleArea(dp))\n",
    "        return ans \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def combine(str1, str2):\n",
    "            ret = \"\"\n",
    "            for i in range(len(str1)):\n",
    "                if str1[i] == \"1\" and str2[i] == \"1\":\n",
    "                    ret += \"1\"\n",
    "                else:\n",
    "                    ret += \"0\"\n",
    "            return ret\n",
    "        \n",
    "        def countSingleRow(str):\n",
    "            maxLen = 0\n",
    "            lenCnt = 0\n",
    "            for i in range(len(str)):\n",
    "                if str[i] == \"1\":\n",
    "                    lenCnt += 1\n",
    "                else:\n",
    "                    lenCnt = 0\n",
    "                maxLen = max(maxLen,lenCnt)\n",
    "            print(str, maxLen)\n",
    "            return maxLen\n",
    "\n",
    "        maxArea = 0\n",
    "        curMatrix = matrix\n",
    "        for roundNo in range(1,len(matrix)+1):\n",
    "            newMatrix = []\n",
    "            if roundNo == 1: \n",
    "                for rowIdx in range(len(curMatrix)):\n",
    "                    res = combine(curMatrix[rowIdx], curMatrix[rowIdx])\n",
    "                    maxArea = max(maxArea,roundNo * countSingleRow(res))\n",
    "                    newMatrix.append(res)\n",
    "            else:\n",
    "                for rowIdx in range(len(curMatrix)-1):\n",
    "                    res = combine(curMatrix[rowIdx], curMatrix[rowIdx+1])\n",
    "                    maxArea = max(maxArea, roundNo * countSingleRow(res))\n",
    "                    newMatrix.append(res)\n",
    "            print(roundNo, maxArea)\n",
    "            curMatrix = newMatrix\n",
    "        \n",
    "        return maxArea\n",
    "\n",
    "# round = 1 max = 5         \n",
    "\n",
    "# round = 2 max = 6\n",
    "# [1,0,1,0,0]\n",
    "# [1,0,1,1,1]\n",
    "# [1,0,0,1,0]\n",
    "\n",
    "# round = 3 max = 3\n",
    "# [1,0,1,0,0]\n",
    "# [1,0,0,1,0]\n",
    "\n",
    "# round = 4 max = 4\n",
    "# [1,0,0,0,0]\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def largestRectangleArea(heights):\n",
    "            r = 0\n",
    "            stack = [0]*len(heights)\n",
    "            ans = 0\n",
    "            n = len(heights)\n",
    "            for i in range(n):\n",
    "                while r>0 and heights[i]<=heights[stack[r-1]]:\n",
    "                    r -= 1\n",
    "                    cur = stack[r]\n",
    "                    left = -1 if r==0 else stack[r-1]\n",
    "                    ans = max(ans,heights[cur]*(i-left-1))\n",
    "                stack[r] = i\n",
    "                r += 1\n",
    "            while r>0:\n",
    "                r-=1\n",
    "                cur = stack[r]\n",
    "                left = -1 if r==0 else stack[r-1]\n",
    "                ans = max(ans,(n-left-1)*heights[cur])\n",
    "            return ans\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        heights = [0]*m\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                heights[j] = 0 if matrix[i][j]==\"0\" else heights[j]+1\n",
    "            ans = max(ans,largestRectangleArea(heights))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])+2\n",
    "        res=0\n",
    "        arrnum=[0]*n\n",
    "\n",
    "        for i in range(m):\n",
    "            stack=[0]           \n",
    "            for j in range(1,n-1):\n",
    "                arrnum[j]= 0  if matrix[i][j-1]=='0' else arrnum[j]+1\n",
    "\n",
    "            for k in range(1,n):\n",
    "                while stack and arrnum[k]<arrnum[stack[-1]]:\n",
    "                    cur_height=arrnum[stack.pop()]\n",
    "                    cur_width=k-1-stack[-1]\n",
    "                    res=max(res,cur_height*cur_width)\n",
    "                stack.append(k)\n",
    "        \n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        \n",
    "#         def maxheights(heights, res):\n",
    "#             st = [0]\n",
    "            \n",
    "#             for i in range(1, len(heights)):\n",
    "#                 while st and heights[i] < heights[st[-1]]:\n",
    "#                     mid = st.pop()\n",
    "#                     s = heights[mid] * (i - st[-1] - 1)\n",
    "#                     res = max(res, s)\n",
    "#                 st.append(i)\n",
    "#             return res\n",
    "#         if not matrix:\n",
    "#             return 0\n",
    "#         matrix = [list(matrix[i]) for i in range(len(matrix))]\n",
    "#         heights = [0] * (len(matrix[0]) + 2)\n",
    "#         result = 0\n",
    "#         for i in range(len(matrix)):\n",
    "#             for j in range(len(matrix[0])):\n",
    "#                 if matrix[i][j] == \"1\":\n",
    "#                     heights[j+1] += 1\n",
    "#                 else:\n",
    "#                     heights[j+1] = 0\n",
    "#                 result = maxheights(heights, result)\n",
    "#         return result\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def maxheight(height: List, res: int):\n",
    "            stack = [-1]   \n",
    "            for i, num in enumerate(height):\n",
    "                while stack[-1] != -1 and height[stack[-1]] > num:\n",
    "                    pre_i = stack.pop()\n",
    "                    res = max(res, (i - stack[-1] - 1) * height[pre_i])\n",
    "                stack.append(i)\n",
    "            while stack[-1] != -1:\n",
    "                pre_i = stack.pop()\n",
    "                res = max(res, (len(height) - stack[-1] - 1) * height[pre_i])\n",
    "            return res\n",
    "        if not matrix: return 0\n",
    "        heights, ans = [0] * len(matrix[0]), 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '0':\n",
    "                    heights[j] = 0\n",
    "                elif i > 0 and matrix[i - 1][j] == '0':\n",
    "                    heights[j] = int(matrix[i][j])\n",
    "                else: heights[j] += 1\n",
    "            ans = maxheight(heights, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:  return 0\n",
    "        elif not matrix[0]: return 0\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        stack = [0] * (n + 1)\n",
    "        stack[-1] = -1\n",
    "        cnt = 0\n",
    "        \n",
    "        def rowCheck():\n",
    "            dp = [-1]\n",
    "            cnt = 0\n",
    "            for i in range(n+1):\n",
    "                if stack[i] < stack[dp[-1]]:\n",
    "                    while stack[i] < stack[dp[-1]]:\n",
    "                        idx = dp.pop()\n",
    "                        cnt = max(cnt, (i - dp[-1] - 1) * stack[idx])\n",
    "                dp.append(i)\n",
    "\n",
    "            return cnt\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\": stack[j] += 1\n",
    "                else:   stack[j] = 0\n",
    "            \n",
    "            cnt = max(cnt, rowCheck())\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def largestRectangleArea(heights: List[int]) -> int:\n",
    "            # 建立一个单调递增的栈,\n",
    "            # 遇到新元素比他小的时候，开始求以栈顶数为高的面积，其左边界为栈顶的第二个数，右边界为当前数(左右都不包含)。\n",
    "            stack = [-1]\n",
    "            ans = 0\n",
    "            for i, height in enumerate(heights):\n",
    "\n",
    "                while len(stack) > 1 and heights[stack[-1]] > height:\n",
    "                    ans = max(ans, heights[stack.pop()] * (i - stack[-1] - 1))\n",
    "                stack.append(i)\n",
    "\n",
    "            for i in range(len(stack) -1):\n",
    "                ans = max(ans, heights[stack.pop()] * (len(heights) - stack[-1] - 1))\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        heights = [0] * len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                heights[j] = heights[j] + 1 if matrix[i][j] == \"1\" else 0\n",
    "            res = max(res, largestRectangleArea(heights))\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        res = 0 \n",
    "\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == \"0\":\n",
    "                    continue\n",
    "                row = float('inf')\n",
    "                col = 1\n",
    "                for m in range(j, -1, -1):\n",
    "                    if matrix[i][m] == \"0\":\n",
    "                        break \n",
    "                    curr_row = 1\n",
    "                    for n in range(i-1, -1, -1):\n",
    "                        if matrix[n][m] == \"1\":\n",
    "                            curr_row += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    row = min(row, curr_row)\n",
    "                    res = max(res, row * (1 + (j-m)))\n",
    "        return res \n",
    "                    \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        \n",
    "        def buildRightBounds(heights):\n",
    "            right_bounds = list(range(len(heights), 0, -1))\n",
    "            stack = []\n",
    "            for i, h in enumerate(heights):\n",
    "                while len(stack) != 0 and h < stack[-1][1]:\n",
    "                    pre_i, _ = stack.pop()\n",
    "                    right_bounds[pre_i] = i - pre_i\n",
    "                stack.append((i, h))\n",
    "            \n",
    "            return right_bounds\n",
    "\n",
    "        def getMaxS(heights):\n",
    "            right_bounds = buildRightBounds(heights)\n",
    "            left_bounds = buildRightBounds(heights[::-1])[::-1]\n",
    "\n",
    "            max_s = 0\n",
    "            for i in range(len(heights)):\n",
    "                cur_s = (left_bounds[i] + right_bounds[i] - 1) * heights[i]\n",
    "                if cur_s > max_s:\n",
    "                    max_s = cur_s\n",
    "            \n",
    "            return max_s\n",
    "\n",
    "        res = 0\n",
    "        heights = [0] * len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for i in range(len(row)):\n",
    "                if row[i] == '0':\n",
    "                    heights[i] = 0\n",
    "                else:\n",
    "                    heights[i] += 1\n",
    "            \n",
    "            max_s = getMaxS(heights)\n",
    "            if max_s > res:\n",
    "                res = max_s\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        import sys\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        M = len(matrix)\n",
    "        N = len(matrix[0])\n",
    "\n",
    "        def ContinuousOne(row):\n",
    "            res = [0] * (N + 1)\n",
    "            for i in range(N):\n",
    "                if row[i] == \"1\":\n",
    "                    res[i + 1] = res[i] + 1\n",
    "            return res[1:]\n",
    "        ContinuousMatrix = []\n",
    "        for row in matrix:\n",
    "            ContinuousMatrix.append(ContinuousOne(row))\n",
    "        res = 0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                # check every point\n",
    "                minContinuousOne = sys.maxsize\n",
    "                for p in range(i, -1, -1):\n",
    "                    minContinuousOne = min(\n",
    "                        minContinuousOne, ContinuousMatrix[p][j])\n",
    "                    tmp = minContinuousOne * (i - p + 1)\n",
    "                    res = max(res, tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "\n",
    "        if not matrix or not matrix[0]: return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "\n",
    "        heights = [0] * m\n",
    "        maxArea = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                heights[j] = heights[j] + 1 if matrix[i][j] == \"1\" else 0\n",
    "            maxArea = max(maxArea, self.largestRectangleArea(heights))\n",
    "\n",
    "        return maxArea\n",
    "    \n",
    "\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        stack = []\n",
    "        maxArea = 0\n",
    "        n = len(heights)\n",
    "        right = [n] * n\n",
    "        left = [-1] * n\n",
    "        for i, height in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] >= height:\n",
    "                t = stack.pop()\n",
    "                right[t] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "            \n",
    "        for i in range(n):\n",
    "            curRight = right[i] - 1 \n",
    "            curLeft = left[i]\n",
    "            maxArea = max(maxArea, (curRight - curLeft) * heights[i])\n",
    "        return maxArea           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:  return 0\n",
    "        elif not matrix[0]: return 0\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        stack = [0] * (n + 1)\n",
    "        stack[-1] = -1\n",
    "        cnt = 0\n",
    "        \n",
    "        def rowCheck():\n",
    "            dp = [-1]\n",
    "            cnt = 0\n",
    "            for i in range(n+1):\n",
    "                if stack[i] < stack[dp[-1]]:\n",
    "                    while stack[i] < stack[dp[-1]]:\n",
    "                        idx = dp.pop()\n",
    "                        cnt = max(cnt, (i - dp[-1] - 1) * stack[idx])\n",
    "                dp.append(i)\n",
    "\n",
    "            return cnt\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\": stack[j] += 1\n",
    "                else:   stack[j] = 0\n",
    "            \n",
    "            cnt = max(cnt, rowCheck())\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        pre_invert = 1\n",
    "        invert = 0\n",
    "        counts: List[List[int]] = [[0 for _ in range(2)] for _ in range(row)]\n",
    "\n",
    "        def pop_and_calc_len(stack, count):\n",
    "            nonlocal ans\n",
    "            new_len = 0\n",
    "            while stack and count < stack[-1][0]:\n",
    "                last = stack.pop()\n",
    "                new_len += last[1]\n",
    "                ans = max(ans, last[0] * new_len)\n",
    "            return new_len + 1\n",
    "\n",
    "        ans = 0\n",
    "        self.__DEBUG = False\n",
    "        \n",
    "        if self.__DEBUG:  # Add debug output if enabled\n",
    "            print(\"\\n\".join(matrix))\n",
    "        \n",
    "        for c in range(col):\n",
    "            if self.__DEBUG:\n",
    "                print(\"col:\", c, \"i/pi:\", invert, pre_invert)\n",
    "            stack: List[List[int]] = []\n",
    "            for r in range(row):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    new_count = counts[r][invert] = counts[r][pre_invert] + 1\n",
    "                    if not stack or new_count > stack[-1][0]:\n",
    "                        stack.append([new_count, 1])\n",
    "                    elif new_count == stack[-1][0]:\n",
    "                        stack[-1][1] += 1\n",
    "                    else:\n",
    "                        new_len = pop_and_calc_len(stack, new_count)\n",
    "                        stack.append([new_count, new_len])\n",
    "                else:\n",
    "                    counts[r][invert] = 0\n",
    "                    pop_and_calc_len(stack, 0)\n",
    "                \n",
    "                if self.__DEBUG:\n",
    "                    print(counts[r][invert], ans)\n",
    "            \n",
    "            pop_and_calc_len(stack, 0)\n",
    "            \n",
    "            if self.__DEBUG:\n",
    "                print(ans)\n",
    "            \n",
    "            invert, pre_invert = pre_invert, invert\n",
    "        \n",
    "        if self.__DEBUG:\n",
    "            print()\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or len(matrix) == 0:\n",
    "            return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        tot = [0] * m\n",
    "        for row in matrix:\n",
    "            for j, x in enumerate(row):\n",
    "                if x == '0':\n",
    "                    tot[j] = 0\n",
    "                else:\n",
    "                    tot[j] += 1\n",
    "            print(tot)\n",
    "            left, right = [-1] * m, [m] * m\n",
    "            stk = []\n",
    "            for i, x in enumerate(tot):\n",
    "                while stk and tot[stk[-1]] >= x:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    left[i] = stk[-1]\n",
    "                stk.append(i)\n",
    "            stk = []\n",
    "            for i in range(m-1, -1, -1):\n",
    "                while stk and tot[stk[-1]] > tot[i]:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    right[i] = stk[-1]\n",
    "                stk.append(i)\n",
    "                ans = max(ans, tot[i] * (right[i] - left[i] - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def combine(str1, str2):\n",
    "            ret = \"\"\n",
    "            for i in range(len(str1)):\n",
    "                if str1[i] == \"1\" and str2[i] == \"1\":\n",
    "                    ret += \"1\"\n",
    "                else:\n",
    "                    ret += \"0\"\n",
    "            return ret\n",
    "        \n",
    "        def countSingleRow(str):\n",
    "            maxLen = 0\n",
    "            lenCnt = 0\n",
    "            for i in range(len(str)):\n",
    "                if str[i] == \"1\":\n",
    "                    lenCnt += 1\n",
    "                else:\n",
    "                    lenCnt = 0\n",
    "                maxLen = max(maxLen,lenCnt)\n",
    "            print(str, maxLen)\n",
    "            return maxLen\n",
    "\n",
    "        maxArea = 0\n",
    "        curMatrix = matrix\n",
    "        for roundNo in range(1,len(matrix)+1):\n",
    "            newMatrix = []\n",
    "            if roundNo == 1: \n",
    "                for rowIdx in range(len(curMatrix)):\n",
    "                    res = combine(curMatrix[rowIdx], curMatrix[rowIdx])\n",
    "                    maxArea = max(maxArea,roundNo * countSingleRow(res))\n",
    "                    newMatrix.append(res)\n",
    "            else:\n",
    "                for rowIdx in range(len(curMatrix)-1):\n",
    "                    res = combine(curMatrix[rowIdx], curMatrix[rowIdx+1])\n",
    "                    maxArea = max(maxArea, roundNo * countSingleRow(res))\n",
    "                    newMatrix.append(res)\n",
    "            print(roundNo, maxArea)\n",
    "            curMatrix = newMatrix\n",
    "        \n",
    "        return maxArea\n",
    "\n",
    "# round = 1 max = 5         \n",
    "\n",
    "# round = 2 max = 6\n",
    "# [1,0,1,0,0]\n",
    "# [1,0,1,1,1]\n",
    "# [1,0,0,1,0]\n",
    "\n",
    "# round = 3 max = 3\n",
    "# [1,0,1,0,0]\n",
    "# [1,0,0,1,0]\n",
    "\n",
    "# round = 4 max = 4\n",
    "# [1,0,0,0,0]\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left_index, right_index = [0] * n, [0] * n\n",
    "\n",
    "        my_stack = []\n",
    "        for i in range(n):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            left_index[i] = my_stack[-1] if len(my_stack)!= 0 else -1\n",
    "            my_stack.append(i)\n",
    "        \n",
    "        my_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            right_index[i] = my_stack[-1] if len(my_stack)!= 0 else n\n",
    "            my_stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right_index[i] - left_index[i] - 1) * heights[i])\n",
    "        return ans\n",
    "    \n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        left_continue_1 = [[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == '1':\n",
    "                    left_continue_1[i][j] = left_continue_1[i][j-1] + 1 if j != 0 else 1;\n",
    "        ans = 0\n",
    "        for j in range(m): # 列\n",
    "            # ans_1 = self.largestRectangleArea([left_continue_1[i][j] for i in range(n)])\n",
    "            # ans = max(ans, ans_1)\n",
    "            up, down = [0] * n, [0] * n\n",
    "            stack = []\n",
    "            for i in range(n):\n",
    "                while len(stack) != 0 and left_continue_1[stack[-1]][j] >= left_continue_1[i][j]:\n",
    "                    stack.pop()\n",
    "                up[i] = stack[-1] if len(stack) != 0 else -1\n",
    "                stack.append(i)\n",
    "            \n",
    "            stack = []\n",
    "            for i in range(n-1, -1, -1):\n",
    "                while len(stack) != 0 and left_continue_1[stack[-1]][j] >= left_continue_1[i][j]:\n",
    "                    stack.pop()\n",
    "                down[i] = stack[-1] if len(stack) != 0 else n\n",
    "                stack.append(i)\n",
    "            \n",
    "            # print([left_continue_1[i][j] for i in range(n)])\n",
    "            # print(up)\n",
    "            # print(down)\n",
    "            # print('----')\n",
    "            \n",
    "            for i in range(n):\n",
    "                ans_1 = (down[i] - up[i] - 1) * left_continue_1[i][j]\n",
    "                ans = max(ans, ans_1)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        dp = [[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = 0 if matrix[i][0]==\"0\" else 1\n",
    "            for j in range(1, m):\n",
    "                dp[i][j] = 0 if matrix[i][j]==\"0\" else dp[i][j-1]+1\n",
    "        res = 0\n",
    "        for j in range(m):\n",
    "            stack = []\n",
    "            up = [0] * n\n",
    "            down = [n] * n\n",
    "            for i in range(n):\n",
    "                while stack and dp[i][j] <= dp[stack[-1]][j]:\n",
    "                    down[stack[-1]] = i\n",
    "                    stack.pop()\n",
    "                up[i] = stack[-1] if stack else -1\n",
    "                stack.append(i)\n",
    "            for i in range(n):\n",
    "                h = down[i] - up[i] - 1\n",
    "                S = h * dp[i][j]\n",
    "                res = max(res, S)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        heights = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    if i == 0:\n",
    "                        heights[i][j] = 1\n",
    "                    else:\n",
    "                        heights[i][j] = heights[i-1][j] + 1\n",
    "        def dfs(height):\n",
    "            height = [0] + height + [0]\n",
    "            n = len(height)\n",
    "            stack = [0]\n",
    "            tmp = 0\n",
    "            for i in range(1, n):\n",
    "                if height[i] > height[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                elif height[i] == height[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and height[i] < height[stack[-1]]:\n",
    "                        index = stack.pop()\n",
    "                        h = height[index]\n",
    "                        if stack:\n",
    "                            tmp = max(tmp, h * (i-stack[-1]-1))\n",
    "                    stack.append(i)\n",
    "            return tmp\n",
    "        res = 0\n",
    "        for height in heights:\n",
    "            res = max(res, dfs(height))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        all_heights = []\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            heights = [0] * (n + 2)\n",
    "            for j in range(n):\n",
    "                k = i\n",
    "                while k >= 0 and matrix[k][j] == \"1\":\n",
    "                    k -= 1\n",
    "                    heights[j + 1] += 1\n",
    "            \n",
    "            all_heights.append(heights)\n",
    "        \n",
    "\n",
    "        res = 0\n",
    "        for heights in all_heights:\n",
    "            stack = []\n",
    "            for i in range(len(heights)):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur = stack.pop()\n",
    "                    res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not matrix: return 0\n",
    "        # all_heights = []\n",
    "        # m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        # for i in range(m - 1, -1, -1):\n",
    "        #     heights = [0] * (n + 2)\n",
    "        #     for j in range(n):\n",
    "        #         k = i\n",
    "        #         while k >= 0 and matrix[k][j] == \"1\":\n",
    "        #             heights[j + 1] += 1\n",
    "        #             k -= 1\n",
    "            \n",
    "        #     all_heights.append(heights)\n",
    "    \n",
    "\n",
    "        \n",
    "        # res = 0\n",
    "        # for heights in all_heights:\n",
    "        #     stack = []\n",
    "        #     for i in range(len(heights)):\n",
    "        #         while stack and heights[stack[-1]] > heights[i]:\n",
    "        #             cur = stack.pop()\n",
    "        #             res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                \n",
    "        #         stack.append(i)\n",
    "        \n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        method  = 'mine'\n",
    "        if method == 'mine':\n",
    "            m = len(matrix)\n",
    "            if m == 0: return 0\n",
    "                    \n",
    "            n = len(matrix[0])\n",
    "            temp = [[0] * n for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                cnt = 0\n",
    "                for j in range(n):\n",
    "                    if matrix[i][j] == '0':\n",
    "                        temp[i][j] = 0\n",
    "                        cnt = 0\n",
    "                    else:\n",
    "                        cnt += 1\n",
    "                        temp[i][j] = cnt\n",
    "            if m == 1:\n",
    "                return max(temp[0])\n",
    "            #print(temp)\n",
    "            res = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if temp[i][j] == 0: continue\n",
    "                    x, y = 0, 0\n",
    "                    while i - x >= 0 and temp[i - x][j] >= temp[i][j]:\n",
    "                        x += 1\n",
    "                    while i + y < m and temp[i + y][j] >= temp[i][j]:\n",
    "                        y += 1\n",
    "                    \n",
    "                    res = max(res, temp[i][j] * (y + x - 1))\n",
    "                    #print(i,j,x,y,res)\n",
    "            return res\n",
    "                         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        pre_invert = 1\n",
    "        invert = 0\n",
    "        counts: List[List[int]] = [[0 for _ in range(2)] for _ in range(row)]\n",
    "\n",
    "        def pop_and_calc_len(stack, count):\n",
    "            nonlocal ans\n",
    "            new_len = 0\n",
    "            while stack and count < stack[-1][0]:\n",
    "                last = stack.pop()\n",
    "                new_len += last[1]\n",
    "                ans = max(ans, last[0] * new_len)\n",
    "            return new_len + 1\n",
    "\n",
    "        ans = 0\n",
    "        # print(\"\\n\".join(matrix))\n",
    "        for c in range(col):\n",
    "            # print(\"col:\", c, \"i/pi:\", invert, pre_invert)\n",
    "            stack: List[List[int]] = []\n",
    "            for r in range(row):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    new_count = counts[r][invert] = counts[r][pre_invert] + 1\n",
    "                    if not stack or new_count > stack[-1][0]:\n",
    "                        stack.append([new_count, 1])\n",
    "                    elif new_count == stack[-1][0]:\n",
    "                        stack[-1][1] += 1\n",
    "                    else:\n",
    "                        new_len = pop_and_calc_len(stack, new_count)\n",
    "                        stack.append([new_count, new_len])\n",
    "                else:\n",
    "                    counts[r][invert] = 0\n",
    "                    pop_and_calc_len(stack, 0)\n",
    "                # print(counts[r][invert], ans)\n",
    "            pop_and_calc_len(stack, 0)\n",
    "            # print(ans)\n",
    "            invert, pre_invert = pre_invert, invert\n",
    "        # print(\"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        pre_invert = 1\n",
    "        invert = 0\n",
    "        heights: List[List[int]] = [[0 for _ in range(2)] for _ in range(row)]\n",
    "\n",
    "        ans = 0\n",
    "        for c in range(col):\n",
    "            stack = []\n",
    "            up = [0 for _ in range(row)]\n",
    "            down = [0 for _ in range(row)]\n",
    "            \n",
    "            stack = []\n",
    "            for r in range(row):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    heights[r][invert] = heights[r][pre_invert] + 1\n",
    "                else:\n",
    "                    heights[r][invert] = 0\n",
    "                while stack and heights[stack[-1]][invert] >= heights[r][invert]:\n",
    "                    stack.pop()\n",
    "                up[r] = stack[-1] if stack else -1\n",
    "                stack.append(r)\n",
    "            \n",
    "            stack = []\n",
    "            for r in reversed(range(row)):\n",
    "                while stack and heights[stack[-1]][invert] >= heights[r][invert]:\n",
    "                    stack.pop()\n",
    "                down[r] = stack[-1] if stack else row\n",
    "                stack.append(r)\n",
    "            \n",
    "            for r in range(row):\n",
    "                ans = max(ans, heights[r][invert] * (down[r] - up[r] - 1))\n",
    "\n",
    "            invert, pre_invert = pre_invert, invert\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        left = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '1':\n",
    "                    left[i][j] += left[i][j-1] + 1 if j > 0 else 1\n",
    "        ans = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '0': continue\n",
    "                w = left[i][j]\n",
    "                ans = max(ans, w)\n",
    "                for k in range(i-1, -1, -1):\n",
    "                    w = min(w, left[k][j])\n",
    "                    if w == 0: break\n",
    "                    ans = max(ans, w * (i - k + 1))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        pre_invert = 1\n",
    "        invert = 0\n",
    "        counts: List[List[int]] = [[0 for _ in range(2)] for _ in range(row)]\n",
    "\n",
    "        ans = 0\n",
    "        # print(\"\\n\".join(matrix))\n",
    "        for c in range(col):\n",
    "            # print(\"col:\", c, \"i/pi:\", invert, pre_invert)\n",
    "            stack = []\n",
    "            for r in range(row):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    count = counts[r][invert] = counts[r][pre_invert] + 1\n",
    "                    if not stack or count > stack[-1][0]:\n",
    "                        stack.append([count, 1])\n",
    "                    elif count == stack[-1][0]:\n",
    "                        stack[-1][1] += 1\n",
    "                    else:\n",
    "                        new_len = 0\n",
    "                        while stack and count < stack[-1][0]:\n",
    "                            last = stack.pop()\n",
    "                            new_len += last[1]\n",
    "                            ans = max(ans, last[0] * new_len)\n",
    "                        stack.append([count, new_len + 1])\n",
    "                else:\n",
    "                    counts[r][invert] = 0\n",
    "\n",
    "                    new_len = 0\n",
    "                    while stack:\n",
    "                        last = stack.pop()\n",
    "                        new_len += last[1]\n",
    "                        ans = max(ans, last[0] * new_len)\n",
    "                # print(counts[r][invert], ans)\n",
    "            new_len = 0\n",
    "            while stack:\n",
    "                last = stack.pop()\n",
    "                new_len += last[1]\n",
    "                ans = max(ans, last[0] * new_len)\n",
    "            # print(ans)\n",
    "            invert, pre_invert = pre_invert, invert\n",
    "        # print(\"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        \n",
    "        def maxheights(heights, res):\n",
    "            st = [0]\n",
    "            \n",
    "            for i in range(1, len(heights)):\n",
    "                while st and heights[i] < heights[st[-1]]:\n",
    "                    mid = st.pop()\n",
    "                    s = heights[mid] * (i - st[-1] - 1)\n",
    "                    res = max(res, s)\n",
    "                st.append(i)\n",
    "            return res\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        matrix = [list(matrix[i]) for i in range(len(matrix))]\n",
    "        heights = [0] * (len(matrix[0]) + 2)\n",
    "        result = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == \"0\":\n",
    "                    heights[j+1] = 0\n",
    "                else:\n",
    "                    heights[j+1] += 1\n",
    "            # print(heights)\n",
    "            result = maxheights(heights, result)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        row = len(matrix)\n",
    "        if row == 0:\n",
    "            return 0\n",
    "        col = len(matrix[0])\n",
    "        if col == 0:\n",
    "            return 0\n",
    "\n",
    "        left = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if matrix[r][c] == '1':\n",
    "                    if c == 0:\n",
    "                        left[r][c] = 1\n",
    "                    else:\n",
    "                        left[r][c] = left[r][c-1] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for c in range(col):\n",
    "            up = [0] * row \n",
    "            down = [0] * row\n",
    "            max_stack = []\n",
    "            for r in range(row):\n",
    "                while max_stack and left[max_stack[-1]][c] >= left[r][c]:\n",
    "                    max_stack.pop()\n",
    "                if max_stack:\n",
    "                    up[r] = max_stack[-1]\n",
    "                else:\n",
    "                    up[r] = -1\n",
    "                max_stack.append(r)\n",
    "            max_stack.clear()\n",
    "            for r in range(row-1, -1, -1):\n",
    "                while max_stack and left[max_stack[-1]][c] >= left[r][c]:\n",
    "                    max_stack.pop()\n",
    "                if max_stack:\n",
    "                    down[r] = max_stack[-1]\n",
    "                else:\n",
    "                    down[r] = row \n",
    "                max_stack.append(r)\n",
    "            for r in range(row):\n",
    "                res = max(res, (down[r] - up[r] - 1) * left[r][c])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix):\n",
    "        def largestRectangleArea(heights, maxmun):\n",
    "            dp = [[0 for i in range(len(heights))] for j in range(len(heights))]\n",
    "\n",
    "            # dp计算最小高度\n",
    "            for i in range(len(heights)):\n",
    "                for j in range(i, len(heights)):\n",
    "                    if i == j or heights[j] < dp[i][j-1]:\n",
    "                        dp[i][j] = heights[j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "\n",
    "                    # 计算dp数组的同时也是在枚举[i:j]，因此可以将面积计算也合并到同一个循环之中。\n",
    "                    s = (j-i+1) * dp[i][j]   \n",
    "                    maxmun = max(maxmun, s)\n",
    "            return maxmun\n",
    "        if not matrix: \n",
    "            return 0\n",
    "        heights, ans = [0] * len(matrix[0]), 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '0':\n",
    "                    heights[j] = 0\n",
    "                elif i > 0 and matrix[i - 1][j] == '0':\n",
    "                    heights[j] = int(matrix[i][j])\n",
    "                else: \n",
    "                    heights[j] += 1\n",
    "            ans = largestRectangleArea(heights, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        pre_invert = 1\n",
    "        invert = 0\n",
    "        heights: List[List[int]] = [[0 for _ in range(2)] for _ in range(row)]\n",
    "        up = [0 for _ in range(row)]\n",
    "        down = [0 for _ in range(row)]\n",
    "\n",
    "        ans = 0\n",
    "        for c in range(col):\n",
    "            stack = []\n",
    "            \n",
    "            \n",
    "            stack = []\n",
    "            for r in range(row):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    heights[r][invert] = heights[r][pre_invert] + 1\n",
    "                else:\n",
    "                    heights[r][invert] = 0\n",
    "                while stack and heights[stack[-1]][invert] >= heights[r][invert]:\n",
    "                    stack.pop()\n",
    "                up[r] = stack[-1] if stack else -1\n",
    "                stack.append(r)\n",
    "            \n",
    "            stack = []\n",
    "            for r in reversed(range(row)):\n",
    "                while stack and heights[stack[-1]][invert] >= heights[r][invert]:\n",
    "                    stack.pop()\n",
    "                down[r] = stack[-1] if stack else row\n",
    "                stack.append(r)\n",
    "            \n",
    "            for r in range(row):\n",
    "                ans = max(ans, heights[r][invert] * (down[r] - up[r] - 1))\n",
    "\n",
    "            invert, pre_invert = pre_invert, invert\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        \n",
    "        def maxheights(heights, res):\n",
    "            st = [0]\n",
    "            \n",
    "            for i in range(1, len(heights)):\n",
    "                while st and heights[i] < heights[st[-1]]:\n",
    "                    mid = st.pop()\n",
    "                    s = heights[mid] * (i - st[-1] - 1)\n",
    "                    res = max(res, s)\n",
    "                st.append(i)\n",
    "            return res\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        matrix = [list(matrix[i]) for i in range(len(matrix))]\n",
    "        heights = [0] * (len(matrix[0]) + 2)\n",
    "        result = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == \"0\":\n",
    "                    heights[j+1] = 0\n",
    "                else:\n",
    "                    heights[j+1] += 1\n",
    "            print(heights)\n",
    "            result = maxheights(heights, result)\n",
    "        return result\n",
    "# class Solution:\n",
    "#     def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "#         def maxheight(height: List, res: int):\n",
    "#             stack = [-1]   \n",
    "#             for i, num in enumerate(height):\n",
    "#                 while stack[-1] != -1 and height[stack[-1]] > num:\n",
    "#                     pre_i = stack.pop()\n",
    "#                     res = max(res, (i - stack[-1] - 1) * height[pre_i])\n",
    "#                 stack.append(i)\n",
    "#             while stack[-1] != -1:\n",
    "#                 pre_i = stack.pop()\n",
    "#                 res = max(res, (len(height) - stack[-1] - 1) * height[pre_i])\n",
    "#             return res\n",
    "#         if not matrix: return 0\n",
    "#         heights, ans = [0] * len(matrix[0]), 0\n",
    "#         for i in range(len(matrix)):\n",
    "#             for j in range(len(matrix[0])):\n",
    "#                 if matrix[i][j] == '0':\n",
    "#                     heights[j] = 0\n",
    "#                 elif i > 0 and matrix[i - 1][j] == '0':\n",
    "#                     heights[j] = int(matrix[i][j])\n",
    "#                 else: heights[j] += 1\n",
    "#             ans = maxheight(heights, ans)\n",
    "#         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        import sys\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        M = len(matrix)\n",
    "        N = len(matrix[0])\n",
    "\n",
    "        def ContinuousOne(row):\n",
    "            res = [0] * (N + 1)\n",
    "            for i in range(N):\n",
    "                if row[i] == \"1\":\n",
    "                    res[i + 1] = res[i] + 1\n",
    "            return res[1:]\n",
    "        ContinuousMatrix = []\n",
    "        for row in matrix:\n",
    "            ContinuousMatrix.append(ContinuousOne(row))\n",
    "        res = 0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                # check every point\n",
    "                minContinuousOne = sys.maxsize\n",
    "                for p in range(i, -1, -1):\n",
    "                    minContinuousOne = min(\n",
    "                        minContinuousOne, ContinuousMatrix[p][j])\n",
    "                    tmp = minContinuousOne * (i - p + 1)\n",
    "                    res = max(res, tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        pre_invert = 1\n",
    "        invert = 0\n",
    "        heights: List[List[int]] = [[0 for _ in range(2)] for _ in range(row)]\n",
    "        up = [0 for _ in range(row)]\n",
    "        down = [0 for _ in range(row)]\n",
    "        stack = [0 for _ in range(row)]\n",
    "        top = -1\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        for c in range(col):\n",
    "            top = -1\n",
    "            for r in range(row):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    heights[r][invert] = heights[r][pre_invert] + 1\n",
    "                else:\n",
    "                    heights[r][invert] = 0\n",
    "                while top > -1 and heights[stack[top]][invert] >= heights[r][invert]:\n",
    "                    top -= 1\n",
    "                up[r] = stack[top] if top > -1 else -1\n",
    "                top += 1\n",
    "                stack[top] = r\n",
    "            \n",
    "            top = -1\n",
    "            for r in reversed(range(row)):\n",
    "                while top > -1 and heights[stack[top]][invert] >= heights[r][invert]:\n",
    "                    top -= 1\n",
    "                down[r] = stack[top] if top > -1 else row\n",
    "                top += 1\n",
    "                stack[top] = r\n",
    "            \n",
    "            for r in range(row):\n",
    "                ans = max(ans, heights[r][invert] * (down[r] - up[r] - 1))\n",
    "\n",
    "            invert, pre_invert = pre_invert, invert\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        heights = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    if i == 0:\n",
    "                        heights[i][j] = 1\n",
    "                    else:\n",
    "                        heights[i][j] = heights[i-1][j] + 1\n",
    "        def dfs(height):\n",
    "            height = [0] + height + [0]\n",
    "            n = len(height)\n",
    "            stack = [0]\n",
    "            tmp = 0\n",
    "            for i in range(1, n):\n",
    "                if height[i] > height[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                elif height[i] == height[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and height[i] < height[stack[-1]]:\n",
    "                        index = stack.pop()\n",
    "                        h = height[index]\n",
    "                        if stack:\n",
    "                            tmp = max(tmp, h * (i-stack[-1]-1))\n",
    "                    stack.append(i)\n",
    "            return tmp\n",
    "        res = 0\n",
    "        for height in heights:\n",
    "            res = max(res, dfs(height))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        left = [[0] * n for _ in range(m)] \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    left[i][j] = 1 if j == 0 else left[i][j - 1] + 1\n",
    "        ret, area = 0, 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '0':\n",
    "                    continue\n",
    "                width = left[i][j]\n",
    "                area = width\n",
    "                for k in range(i - 1, -1, -1):\n",
    "                        width = min(width, left[k][j])\n",
    "                        area = max(area, (i - k + 1) * width)\n",
    "                ret = max(ret, area)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        row = len(matrix)\n",
    "        if row == 0:\n",
    "            return 0\n",
    "        col = len(matrix[0])\n",
    "        if col == 0:\n",
    "            return 0\n",
    "        left = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == '1':\n",
    "                    if j == 0:\n",
    "                        left[i][j] = 1\n",
    "                    else:\n",
    "                        left[i][j] = left[i][j-1] + 1\n",
    "        res = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == '0':\n",
    "                    continue\n",
    "                w = left[i][j]\n",
    "                # a = w\n",
    "                for k in range(i, -1, -1):\n",
    "                    w = min(w, left[k][j])\n",
    "                    # a = max(a, (i-k+1)*w)\n",
    "                    res = max(res, (i-k+1)*w)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            f[0][j] = int(matrix[0][j])\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    f[i][j] = f[i - 1][j] + 1\n",
    "        max_area = 0\n",
    "        stack, index = [0] * n, -1\n",
    "        right_higher = [0] * n\n",
    "        left_higher = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                while index > -1 and f[i][j] < stack[index][0]:\n",
    "                    right_higher[stack[index][1]] = stack[index][2]\n",
    "                    if index - 1 > -1:\n",
    "                        stack[index - 1][2] += stack[index][2] + 1\n",
    "                    index -= 1\n",
    "                stack[index + 1] = [f[i][j], j, 0]\n",
    "                index += 1\n",
    "            while index > -1:\n",
    "                right_higher[stack[index][1]] = stack[index][2]\n",
    "                if index - 1 > -1:\n",
    "                    stack[index - 1][2] += stack[index][2] + 1\n",
    "                index -= 1\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                while index > -1 and f[i][j] < stack[index][0]:\n",
    "                    left_higher[stack[index][1]] = stack[index][2]\n",
    "                    if index - 1 > -1:\n",
    "                        stack[index - 1][2] += stack[index][2] + 1\n",
    "                    index -= 1\n",
    "                stack[index + 1] = [f[i][j], j, 0]\n",
    "                index += 1\n",
    "            while index > -1:\n",
    "                left_higher[stack[index][1]] = stack[index][2]\n",
    "                if index - 1 > -1:\n",
    "                    stack[index - 1][2] += stack[index][2] + 1\n",
    "                index -= 1\n",
    "            for j in range(n):\n",
    "                max_area = max(\n",
    "                    max_area,\n",
    "                    f[i][j] * (left_higher[j] + right_higher[j] + 1),\n",
    "                )\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        all_heights = []\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            heights = [0] * (n + 2)\n",
    "            for j in range(n):\n",
    "                k = i\n",
    "                while k >= 0 and matrix[k][j] == \"1\":\n",
    "                    heights[j + 1] += 1\n",
    "                    k -= 1\n",
    "        \n",
    "            all_heights.append(heights)\n",
    "        \n",
    "        res = 0\n",
    "        for heights in all_heights:\n",
    "            stack = []\n",
    "            for i in range(len(heights)):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur = stack.pop()\n",
    "                    res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not matrix: return 0\n",
    "        # all_heights = []\n",
    "        # m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        # for i in range(m - 1, -1, -1):\n",
    "        #     heights = [0] * (n + 2)\n",
    "        #     for j in range(n):\n",
    "        #         k = i\n",
    "        #         while k >= 0 and matrix[k][j] == \"1\":\n",
    "        #             heights[j + 1] += 1\n",
    "        #             k -= 1\n",
    "            \n",
    "        #     all_heights.append(heights)\n",
    "    \n",
    "\n",
    "        \n",
    "        # res = 0\n",
    "        # for heights in all_heights:\n",
    "        #     stack = []\n",
    "        #     for i in range(len(heights)):\n",
    "        #         while stack and heights[stack[-1]] > heights[i]:\n",
    "        #             cur = stack.pop()\n",
    "        #             res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                \n",
    "        #         stack.append(i)\n",
    "        \n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        height=[[0 for _ in range(2+len(matrix[0]))] for _ in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]=='1':\n",
    "                    if i==0:\n",
    "                        height[i][j+1]=1\n",
    "                    else:\n",
    "                        height[i][j+1]=height[i-1][j+1]+1\n",
    "        result=0\n",
    "        \n",
    "        for i in range(len(height)):\n",
    "            st=[0]\n",
    "            for j in range(1,len(height[0])):\n",
    "                if height[i][j]>=height[i][st[-1]]:\n",
    "                    st.append(j)\n",
    "                while len(st)!=0 and height[i][j]<height[i][st[-1]]:\n",
    "                    h=height[i][st[-1]]\n",
    "                    st.pop()\n",
    "                    # if len(st)!=0:\n",
    "                    left=st[-1]\n",
    "                    result=max(result,(j-left-1)*h)\n",
    "                st.append(j)\n",
    "        return result\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left_index, right_index = [0] * n, [0] * n\n",
    "\n",
    "        my_stack = []\n",
    "        for i in range(n):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            left_index[i] = my_stack[-1] if len(my_stack)!= 0 else -1\n",
    "            my_stack.append(i)\n",
    "        \n",
    "        my_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            right_index[i] = my_stack[-1] if len(my_stack)!= 0 else n\n",
    "            my_stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right_index[i] - left_index[i] - 1) * heights[i])\n",
    "        return ans\n",
    "    \n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        left_continue_1 = [[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == '1':\n",
    "                    left_continue_1[i][j] = left_continue_1[i][j-1] + 1 if j != 0 else 1;\n",
    "        ans = 0\n",
    "        for j in range(m): # 列\n",
    "            ans_1 = self.largestRectangleArea([left_continue_1[i][j] for i in range(n)])\n",
    "            ans = max(ans, ans_1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        left = [ [ 0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"0\":\n",
    "                    left[i][j] = 0\n",
    "                else:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                w = left[i][j]\n",
    "                res = max(res, w)\n",
    "                for k in range(i-1, -1, -1):\n",
    "                    w = min(w, left[k][j])\n",
    "                    res = max(res, (i-k+1)*w)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        def ares(list1):\n",
    "            list1.append(0)\n",
    "            stack,res=[],[]\n",
    "            stack.append(-1)\n",
    "            width,j,i=0,0,0\n",
    "            while i<len(list1):\n",
    "                if stack[j]==-1:\n",
    "                    stack.append(i)\n",
    "                    width+=1\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                elif list1[stack[j]]<list1[i] and stack[j]!=-1:\n",
    "                    stack.append(i)\n",
    "                    width+=1\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    a=stack.pop()\n",
    "                    j-=1\n",
    "                    m2=list1[a]*(width-stack[j]-1)\n",
    "                    res.append(m2)\n",
    "            return max(res)\n",
    "\n",
    "\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "        left = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i!=0:\n",
    "                    if matrix[i][j] == '1' and matrix[i-1][j]!=0:\n",
    "                        left[i][j] = 1+left[i-1][j]\n",
    "                    elif matrix[i][j] == '1':\n",
    "                        left[i][j]=left[i-1][j]\n",
    "                else:\n",
    "                    if matrix[i][j] == '1':\n",
    "                            left[i][j] += 1\n",
    "        \n",
    "        res=0\n",
    "        for i in range(len(left)):\n",
    "            res=max(ares(left[i]),res)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        heights = [0] * (len(matrix[0]) + 1)\n",
    "        max_rect = 0\n",
    "        for index_i in range(len(matrix)):\n",
    "            # 当前行的高度\n",
    "            for index_j in range(len(matrix[0])):\n",
    "                if matrix[index_i][index_j] == '0':\n",
    "                    heights[index_j] = 0\n",
    "                else:\n",
    "                    heights[index_j] += 1\n",
    "            \n",
    "            # 当前行最大矩形\n",
    "            stack = []\n",
    "            for index_j in range(len(heights)):\n",
    "                while stack and heights[stack[-1]] >= heights[index_j]:\n",
    "                    start = stack.pop()\n",
    "                    width = index_j - stack[-1] - 1 if len(stack) > 0 else index_j\n",
    "                    height = heights[start]\n",
    "                    if index_i == 2:\n",
    "                        print(index_i, index_j, width, height)\n",
    "                    max_rect = max(max_rect, width * height)\n",
    "                stack.append(index_j)\n",
    "        return max_rect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        left = [[0] * n for _ in range(m)] \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    left[i][j] = 1 if j == 0 else left[i][j - 1] + 1\n",
    "        ret, area = 0, 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '0':\n",
    "                    continue\n",
    "                width = left[i][j]\n",
    "                area = width\n",
    "                for k in range(i - 1, -1, -1):\n",
    "                        width = min(width, left[k][j])\n",
    "                        area = max(area, (i - k + 1) * width)\n",
    "                ret = max(ret, area)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        maxArea = 0\n",
    "\n",
    "        cumsum = [0] * (col + 1)\n",
    "\n",
    "        for i in range(row):\n",
    "            lineMax = 0\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    cumsum[j] += 1\n",
    "                else:\n",
    "                    cumsum[j] = 0\n",
    "\n",
    "            # print(cumsum)\n",
    "\n",
    "            s = []\n",
    "            for j, num in enumerate(cumsum):\n",
    "                minIdx = j\n",
    "                while s and s[-1][0] > num:\n",
    "                    curArea = s[-1][0] * (j - s[-1][1])\n",
    "                    print(s[-1][0], j - s[-1][1], curArea)\n",
    "                    \n",
    "                    lineMax = max(lineMax, curArea)\n",
    "                    lastHeight, lastIdx = s.pop()\n",
    "                    minIdx = lastIdx\n",
    "                s.append([num, minIdx])\n",
    "                # print(s)\n",
    "            # print(\"line max info: %s\"%(lineMax))\n",
    "            maxArea = max(maxArea, lineMax)\n",
    "        return maxArea\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i, s in enumerate(matrix):\n",
    "            for j, c in enumerate(s):\n",
    "                if c == \"1\":\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = dp[i][j] + 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j] + 1\n",
    "        def area(height):\n",
    "            height = [0] + height + [0]\n",
    "            n = len(height)\n",
    "            stack = [0]\n",
    "            res = 0\n",
    "            for i in range(1, n):\n",
    "                if height[i] > height[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                elif height[i] == height[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and height[i] < height[stack[-1]]:\n",
    "                        index = stack.pop()\n",
    "                        h = height[index]\n",
    "                        if stack:\n",
    "                            res = max(res, h*(i-stack[-1]-1))\n",
    "                    stack.append(i)\n",
    "            return res\n",
    "        res = 0\n",
    "        for height in dp:\n",
    "            res = max(res, area(height))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix: return 0\n",
    "        all_heights = []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            heights = [0] * (n + 2)\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    k = i\n",
    "                    while matrix[k][j] == \"1\" and k >= 0:\n",
    "                        heights[j + 1] += 1\n",
    "                        k -= 1\n",
    "            \n",
    "            all_heights.append(heights)\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for heights in all_heights:\n",
    "            stack = []\n",
    "            for i in range(len(heights)):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur = stack.pop()\n",
    "                    res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not matrix: return 0\n",
    "        # all_heights = []\n",
    "        # m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        # for i in range(m - 1, -1, -1):\n",
    "        #     heights = [0] * (n + 2)\n",
    "        #     for j in range(n):\n",
    "        #         k = i\n",
    "        #         while k >= 0 and matrix[k][j] == \"1\":\n",
    "        #             heights[j + 1] += 1\n",
    "        #             k -= 1\n",
    "            \n",
    "        #     all_heights.append(heights)\n",
    "    \n",
    "\n",
    "        \n",
    "        # res = 0\n",
    "        # for heights in all_heights:\n",
    "        #     stack = []\n",
    "        #     for i in range(len(heights)):\n",
    "        #         while stack and heights[stack[-1]] > heights[i]:\n",
    "        #             cur = stack.pop()\n",
    "        #             res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                \n",
    "        #         stack.append(i)\n",
    "        \n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "        left = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    left[i][j] = 1 if j == 0 else left[i][j - 1] + 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '0':\n",
    "                    continue\n",
    "                width = left[i][j]\n",
    "                area = width\n",
    "                for k in range(i - 1, -1, -1):\n",
    "                    width = min(width, left[k][j])\n",
    "                    area = max(area, (i - k + 1) * width)\n",
    "\n",
    "                res = max(res, area)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxArea(self, rec):\n",
    "        d = [(-1, 0)]\n",
    "        left = [0]*len(rec)\n",
    "        right = [0]*len(rec)\n",
    "        for i, x in enumerate(rec):\n",
    "            while d[-1][0] != -1 and x <= d[-1][1]:\n",
    "                d.pop(-1)\n",
    "            left[i] = d[-1][0]\n",
    "            d.append((i, x))\n",
    "        d = [(len(rec), 0)]\n",
    "        i = len(rec) - 1\n",
    "        while i >= 0:\n",
    "            while d[-1][0] != len(rec) and rec[i] <= d[-1][1]:\n",
    "                d.pop(-1)\n",
    "            right[i] = d[-1][0]\n",
    "            d.append((i, rec[i]))\n",
    "            i = i - 1\n",
    "        max_size = 0\n",
    "        for i, h in enumerate(rec):\n",
    "            max_size = max(h*(right[i] - left[i] - 1), max_size)\n",
    "        return max_size\n",
    "\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        max_area = 0\n",
    "        m = len(matrix)\n",
    "        if m == 0: return 0\n",
    "        n = len(matrix[0])\n",
    "        if n == 0: return 0\n",
    "        left = []\n",
    "        for i, row in enumerate(matrix):\n",
    "            left.append([0]*n)\n",
    "            for j, c in enumerate(row):\n",
    "                if j == 0:\n",
    "                    left[i][j] = int(c)\n",
    "                elif c == '0':\n",
    "                    left[i][j] = 0\n",
    "                elif c == '1':\n",
    "                    left[i][j] = (int(left[i][j-1]) + 1)\n",
    "\n",
    "        for k in range(n):\n",
    "            max_area = max(max_area, self.maxArea([left[i][k] for i in range(m)]))\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        height=[[0 for _ in range(2+len(matrix[0]))] for _ in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]=='1':\n",
    "                    if i==0:\n",
    "                        height[i][j+1]=1\n",
    "                    else:\n",
    "                        height[i][j+1]=height[i-1][j+1]+1\n",
    "        result=0\n",
    "        \n",
    "        for i in range(len(height)):\n",
    "            st=[0]\n",
    "            for j in range(1,len(height[0])):\n",
    "                if height[i][j]>=height[i][st[-1]]:\n",
    "                    st.append(j)\n",
    "                while len(st)!=0 and height[i][j]<height[i][st[-1]]:\n",
    "                    h=height[i][st[-1]]\n",
    "                    st.pop()\n",
    "                    if len(st)!=0:\n",
    "                        left=st[-1]\n",
    "                        result=max(result,(j-left-1)*h)\n",
    "                st.append(j)\n",
    "                # print(j)\n",
    "        return result\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        all_heights = []\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            heights = [0] * (n + 2)\n",
    "            for j in range(n):\n",
    "                k = i\n",
    "                while k >= 0 and matrix[k][j] == \"1\":\n",
    "                    heights[j + 1] += 1\n",
    "                    k -= 1\n",
    "        \n",
    "            all_heights.append(heights)\n",
    "        \n",
    "        # print(all_heights)\n",
    "        res = 0\n",
    "\n",
    "        for heights in all_heights:\n",
    "            stack = []\n",
    "            for i in range(len(heights)):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur = stack.pop()\n",
    "                    res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                \n",
    "                stack.append(i)\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not matrix: return 0\n",
    "        # all_heights = []\n",
    "        # m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        # for i in range(m - 1, -1, -1):\n",
    "        #     heights = [0] * (n + 2)\n",
    "        #     for j in range(n):\n",
    "        #         k = i\n",
    "        #         while k >= 0 and matrix[k][j] == \"1\":\n",
    "        #             heights[j + 1] += 1\n",
    "        #             k -= 1\n",
    "            \n",
    "        #     all_heights.append(heights)\n",
    "    \n",
    "\n",
    "        \n",
    "        # res = 0\n",
    "        # for heights in all_heights:\n",
    "        #     stack = []\n",
    "        #     for i in range(len(heights)):\n",
    "        #         while stack and heights[stack[-1]] > heights[i]:\n",
    "        #             cur = stack.pop()\n",
    "        #             res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                \n",
    "        #         stack.append(i)\n",
    "        \n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix or not matrix[0]: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        all_heights = []\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            heights = [0] * (n + 2)\n",
    "            for j in range(n):\n",
    "                k = i\n",
    "                while k >= 0 and matrix[k][j] == \"1\":\n",
    "                    k -= 1\n",
    "                    heights[j + 1] += 1\n",
    "\n",
    "            all_heights.append(heights)\n",
    "        \n",
    "        res = 0\n",
    "        for heights in all_heights:\n",
    "            stack = []\n",
    "            for i in range(len(heights)):\n",
    "                while stack and heights[stack[-1]] > heights[i]:\n",
    "                    cur = stack.pop()\n",
    "                    res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not matrix: return 0\n",
    "        # all_heights = []\n",
    "        # m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        # for i in range(m - 1, -1, -1):\n",
    "        #     heights = [0] * (n + 2)\n",
    "        #     for j in range(n):\n",
    "        #         k = i\n",
    "        #         while k >= 0 and matrix[k][j] == \"1\":\n",
    "        #             heights[j + 1] += 1\n",
    "        #             k -= 1\n",
    "            \n",
    "        #     all_heights.append(heights)\n",
    "    \n",
    "\n",
    "        \n",
    "        # res = 0\n",
    "        # for heights in all_heights:\n",
    "        #     stack = []\n",
    "        #     for i in range(len(heights)):\n",
    "        #         while stack and heights[stack[-1]] > heights[i]:\n",
    "        #             cur = stack.pop()\n",
    "        #             res = max(res, heights[cur] * (i - stack[-1] - 1))\n",
    "                \n",
    "        #         stack.append(i)\n",
    "        \n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j] + 1\n",
    "        def dfs(height):\n",
    "            height = [0] + height + [0]\n",
    "            n = len(height)\n",
    "            res = 0\n",
    "            stack = [0]\n",
    "            for i in range(1, n):\n",
    "                if height[i] > height[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                elif height[i] == height[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and height[i] < height[stack[-1]]:\n",
    "                        index = stack.pop()\n",
    "                        h = height[index]\n",
    "                        if stack:\n",
    "                            res = max(res, h * (i-stack[-1]-1))\n",
    "                    stack.append(i)\n",
    "            return res\n",
    "        res = 0\n",
    "        for height in dp:\n",
    "            res = max(res, dfs(height))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        height=[[0 for _ in range(2+len(matrix[0]))] for _ in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]=='1':\n",
    "                    if i==0:\n",
    "                        height[i][j+1]=1\n",
    "                    else:\n",
    "                        height[i][j+1]=height[i-1][j+1]+1\n",
    "        result=0\n",
    "        \n",
    "        for i in range(len(height)):\n",
    "            st=[0]\n",
    "            for j in range(1,len(height[0])):\n",
    "                if height[i][j]>=height[i][st[-1]]:\n",
    "                    st.append(j)\n",
    "                while len(st)!=0 and height[i][j]<height[i][st[-1]]:\n",
    "                    h=height[i][st[-1]]\n",
    "                    st.pop()\n",
    "                    left=st[-1]\n",
    "                    result=max(result,(j-left-1)*h)\n",
    "                st.append(j)\n",
    "        return result\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        \n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        # process matrix\n",
    "        mat = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == '1':\n",
    "                    mat[i][j] = 1 if j == 0 else mat[i][j-1]+1\n",
    "        # print(mat)\n",
    "        res = 0\n",
    "        for j in range(col):\n",
    "            top = []\n",
    "            down = []\n",
    "            stack = []\n",
    "            for i in range(row):\n",
    "                while stack and mat[stack[-1]][j] >= mat[i][j]:\n",
    "                    stack.pop()\n",
    "                top.append(stack[-1] if stack else -1)\n",
    "                stack.append(i)\n",
    "            stack = []\n",
    "            for i in range(row-1,-1,-1):\n",
    "                while stack and mat[stack[-1]][j] >= mat[i][j]:\n",
    "                    stack.pop()\n",
    "                down.insert(0,stack[-1] if stack else row)\n",
    "                stack.append(i)\n",
    "            # print(top)\n",
    "            # print(down)\n",
    "            for i in range(row):\n",
    "                height = down[i]-top[i]-1\n",
    "                area = height*mat[i][j]\n",
    "                res = max(res,area)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[str]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        int_matrix = [[int(char) for char in row] for row in matrix]\n",
    "        print(int_matrix)\n",
    "        m, n = len(int_matrix), len(int_matrix[0])\n",
    "        new_matrix = [[0]*n for _ in range(m)]\n",
    "        new_matrix[0] = int_matrix[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                new_matrix[i][j] = (new_matrix[i-1][j] + 1) if int_matrix[i][j] == 1 else 0\n",
    "\n",
    "        def getMaxArea(lst):\n",
    "            n = len(lst)\n",
    "            left, right = [-1]*n, [n]*n\n",
    "            st = []\n",
    "            for i in range(n):\n",
    "                while st and lst[st[-1]] >= lst[i]:\n",
    "                    st.pop()\n",
    "                if st: left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            st = []\n",
    "            for i in range(n-1, -1, -1):\n",
    "                while st and lst[st[-1]] >= lst[i]:\n",
    "                    st.pop()\n",
    "                if st: right[i] = st[-1]\n",
    "                st.append(i)\n",
    "            maxarea = 0\n",
    "            for i in range(n):\n",
    "                maxarea = max(maxarea, (right[i]-left[i]-1)*lst[i])\n",
    "            return maxarea\n",
    "\n",
    "        maxarea_mat = 0\n",
    "        for l in new_matrix:\n",
    "            maxarea_mat = max(maxarea_mat, getMaxArea(l))\n",
    "        return maxarea_mat\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
